package com.tucc.hello.leetcode.no801_1200.no815;

import cn.hutool.core.io.FileUtil;
import cn.hutool.json.JSONArray;
import cn.hutool.json.JSONUtil;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] routes = {{1, 2, 7}, {3, 6, 7}};
        int source = 1;
        int target = 6;
        String content = FileUtil.readUtf8String("E:/test/no815.txt");
        String[] line = content.split("\\r\\n");
        String dataStr = line[0].trim();
        List<JSONArray> dataStrs = JSONUtil.toList(dataStr, JSONArray.class);
        routes = new int[dataStrs.size()][];
        for (int i = 0; i < routes.length; i++) {
            routes[i] = Arrays.stream(dataStrs.get(i).toArray()).mapToInt(o -> ((Integer) o).intValue()).toArray();
        }
        source = Integer.valueOf(line[1]);
        target = Integer.valueOf(line[2]);
        System.out.println(solution.numBusesToDestination(routes, source, target));
    }

    public int numBusesToDestination(int[][] routes, int source, int target) {
        int count = 0;
        Map<Integer, List<Integer>> routeMap = new HashMap<>();
        List<Integer> startList = new ArrayList<>();
        int targetIndex = -1;
        for (int i = 0; i < routes.length; i++) {
            for (int num : routes[i]) {
                List<Integer> list = routeMap.get(num);
                if (list == null) {
                    list = new ArrayList<>();
                    routeMap.put(num, list);
                }
                list.add(i);
                if (num == source) {
                    startList.add(i);
                }
                if (num == target) {
                    targetIndex = i;
                }
            }
        }
        List<Integer> nextList = null;
        if (targetIndex == -1) {
            return -1;
        }
        if (!startList.isEmpty()) {
            if (source == target) {
                return 0;
            }
        }
        boolean[] visit = new boolean[routes.length];
        while (true) {
            if (startList.isEmpty()) {
                return -1;
            }
            nextList = new ArrayList<>();
            count++;
            for (int index : startList) {
                visit[index] = true;
                int[] curRoute = routes[index];
                for (int i = 0; i < curRoute.length; i++) {
                    if (curRoute[i] == target) {
                        return count;
                    }
                    List<Integer> nextRouteIndexes = routeMap.get(curRoute[i]);
                    for (Integer next : nextRouteIndexes) {
                        if (!visit[next]) {
                            nextList.add(next);
                        }
                    }
                }
            }
            startList = nextList;
        }
    }


}
